package mao.algorithm.redbook.demo28_5;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	//T:1,H:0
	private static int NUMBER_OF_NODE;
	private List<List<Edge>> edges = new ArrayList<>();

	public Graph(int nodeNumber) {
		NUMBER_OF_NODE=nodeNumber;	
	}

	public  Tree bfs(int  root) {
		int[] parent = new int[NUMBER_OF_NODE];
		boolean[] isVisited = new boolean[NUMBER_OF_NODE];
		for (int i = 0;i<NUMBER_OF_NODE;i++) {
			isVisited[i] = false;
		}
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.offer(root);
		for (int i=0;i<parent.length;i++) {
			parent[i] = -2;
		}
		parent[root]=-1;
		isVisited[root]=true;
		
		while(!queue.isEmpty()){
			Integer currentNode = queue.poll();
			List<Edge> list = edges.get(currentNode);
			for(int i=0;i<list.size();i++){
				int childIndex = list.get(i).getV();
				if(isVisited[childIndex] == false){
					parent[childIndex] = currentNode;
					isVisited[childIndex] = true; 
					queue.offer(childIndex);
				}
			}
		}
		
		Tree tree = new Tree(parent);
		return tree;
		
	}

	public  void addEdge(int u,int v) {
		if(edges.size() <= u){
		   edges.add(new ArrayList<Edge>());
		}
		edges.get(u).add(new Edge(u,v));
	}

	public List<List<Integer>> getConnectedGraph(){
//		Tree tree = bfs(0);
//		int numberOfNodeFinded = 0;
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<Integer>();
		int index = 0;
		while(list.size() != NUMBER_OF_NODE ){
	   		if(! list.contains(index)){
	   			Tree tree = bfs(index);
	   			list.addAll(tree.getNodeInTree());
	   			result.add((List<Integer>) new ArrayList<Integer>(tree.getNodeInTree()));
	   		}else{
	   			index++;
	   		}
		}
		return result;
	}
	

	
	public static class Tree{
		int[] parent = new int[NUMBER_OF_NODE];

		public Tree(int[] parent) {
			this.parent = parent.clone();
		}
		
		public List<Integer> getShortPath(int index){
			ArrayList<Integer> path = new ArrayList<Integer>();
			while(parent[index] != -1){
				path.add(index);
				index=parent[index];
			}
			path.add(index);
			return path;
		}
		
		public int getNodeNumberOfTree(){
			int count =0;
			for (int i : parent) {
				if(i != -2){
					count++;
				}
			}
			return count;
			
		}
		public List<Integer> getNodeInTree(){
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int i=0;i<parent.length;i++) {
				if(parent[i] != -2){
					list.add(i);
				}
			}
			return list;
			
		}
	}
	
}
